# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

from python.mypackage import ListNode


class Solution:
    """
    方法：反转链表中指定区间的节点
         一次遍历「穿针引线」反转链表（头插法）
    
    Args:
        head: 链表头节点
        left: 起始位置（从1开始）
        right: 结束位置
        
    Returns:
        反转指定区间后的链表头节点
        
    Time: O(N) - 需要遍历一次链表
    
    Space: O(1) - 只使用常数额外空间
    """
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(-1);
        dummy.next = head
        pre = dummy;
        for _ in range(left - 1):
            pre = pre.next
        cur = pre.next
        for _ in range(right - left):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy.next
        
    """
    方法：使用迭代方式反转链表中指定区间的节点
    
    Args:
        head: 链表头节点
        left: 起始位置（从1开始）
        right: 结束位置
        
    Returns:
        反转指定区间后的链表头节点
        
    Time: O(N) - 需要遍历一次链表
    
    Space: O(1) - 只使用常数额外空间
    """
    def reverseBetween1(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        def reverseLinkedList(head: ListNode):
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
        dummy = ListNode(-1);
        dummy.next = head
        pre = dummy;
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        for _ in range(left - 1):
            pre = pre.next
        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
         # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        curr = right_node.next
        pre.next = None
        right_node.next = None
        # 第 4 步：同第 206 题，反转链表的子区间 
        reverseLinkedList(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return dummy.next